// function ajustMaxHeap(array, index, length) {
//   for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {
//     console.log(i); // i是index的左子
//     // 左子不能超过length，如果右子大，则i++
//     if (i + 1 < length && array[i + 1] > array[i]) {
//       i++;
//     }
//     // i和较大的子对比
//     if (array[index] >= array[i]) {
//       break;
//     } else {
//       [array[index], array[i]] = [array[i], array[index]];
//       index = i;  // 用于更深一层对比
//     }
//   }
// }

// function createMaxHeap(arr, length) {
//   for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
//     ajustMaxHeap(arr, i, length);
//   }
//   return arr;
// }
// var arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
// console.log(createMaxHeap(arr, arr.length));

var arr = [3, 5, 7, 1, 4, 56, 12, 37, 78, 25, 0, 9, 3, 8, 42];
function heapSort(array) {
  creatHeap(array);
  // 交换第一个和最后一个元素，然后重新调整大顶堆
  for (let i = array.length - 1; i > 0; i--) {
    [array[i], array[0]] = [array[0], array[i]];
    adjust(array, 0, i);
  }
  return array;
}
// 构建大顶堆，从第一个非叶子节点开始，进行下沉操作
function creatHeap(array) {
  const len = array.length;
  const start = parseInt(len / 2) - 1;
  for (let i = start; i >= 0; i--) {
    adjust(array, i, len);
  }
}
// 将第target个元素进行下沉，孩子节点有比他大的就下沉
function adjust(array, target, len) {
  console.log(target)
  for (let i = 2 * target + 1; i < len; i = 2 * i + 1) {
    // 找到孩子节点中最大的
    if (i + 1 < len && array[i + 1] > array[i]) {
      i = i + 1;
    }
    // 下沉
    if (array[i] > array[target]) {
      [array[i], array[target]] = [array[target], array[i]]
      target = i;
    } else {
      break;
    }
  }
}
console.log(heapSort(arr));
